/**
 * function: Get_Partner
 * 功能：该函数用来获得某个阶段，某个进程的通信伙伴
*/
int Get_Partner(int my_rank, int phase) {
	// 偶通信阶段，偶数为通信双方的较小进程
	if (phase % 2 == 0) {
		if (my_rank % 2 == 0) {
			return my_rank - 1;
		}
		else {
			return my_rank + 1;
		}
	}
	// 奇通信阶段，奇数为通信双方的较小进程
	else {
		if (my_rank % 2 == 0) {
			return my_rank + 1;
		}
		else {
			return my_rank - 1;
		}
	}
}
 
/**
 * 这个函数用来产生随机数，并分发至各个进程
 */
void Get_Input(int A[], int local_n, int my_rank, int size) {
	int* a = NULL;
	// 主进程动态开辟内存，产生随机数，分发至各个进程
	if (my_rank == 0) {
		a = (int *)malloc(size*sizeof(int));
		CreateData(a, size);
		MPI_Scatter(a, local_n, MPI_INT, A, local_n, MPI_INT, 0, MPI_COMM_WORLD);
		free(a);
	}
	// 其余进程接收随机数
	else {
		MPI_Scatter(a, local_n, MPI_INT, A, local_n, MPI_INT, 0, MPI_COMM_WORLD);
	}
}

 /**
 * Merge_Low
 * 功能：该函数用来合并两个进程的数据，并取较小的一半数据
 */
void Merge_Low(int A[], int B[], int local_n) {
	int* a = (int *)malloc(local_n*sizeof(int));		// 临时数组，倒腾较小的数据
	int p_a = 0, p_b = 0, i = 0;	//分别为A,B,a三个数组的指针
 
	// 这里不同担心数组越界，因为三个数组的大小是相等的
	while (i < local_n) {
		if (A[p_a] < B[p_b]) {
			a[i++] = A[p_a++];
		}
		else {
			a[i++] = B[p_b++];
		}
	}
	// 倒腾一下
	for (i = 0; i < local_n; i++) {
		A[i] = a[i];
	}
	free(a);
}
 
/**
 * 函数名：Merge_High
 * 功能：该函数用来合并两个进程的数据，并取较大的一半数据，与前面的Merge_Low函数类似
 */
void Merge_High(int A[], int B[], int local_n) {
	int p_a = local_n - 1, p_b = local_n - 1, i = local_n - 1;
	int* a = (int *)malloc(local_n*sizeof(int));
	// 注意取最大值需要从后往前面取
	while (i >= 0) {
		if (A[p_a] > B[p_b]) {
			a[i--] = A[p_a--];
		}
		else {
			a[i--] = B[p_b--];
		}
	}
	for (i = 0; i < local_n; i++) {
		A[i] = a[i];
	}
	free(a);
}
 